⟸ pàgina anterior ⟸
Exercici 2 (Tasca 3).
(pumping lemma)

Comptar as i bs no és regular (en general)

Demostreu que els llenguatges següents no són regulars.

  1. \{w\in \{a,b\}^* \mid |w|_a = |w|_b\}
  2. \{w\in \{a,b\}^* \mid |w|_a \geq |w|_b\}
  3. \{w\in \{a,b\}^* \mid |w|_a \leq |w|_b\}
  4. \{w\in \{a,b\}^* \mid |w|_a \neq |w|_b\}
  5. \{w\in \{a,b,c\}^* \mid |w|_a \geq |w|_b \lor |w|_b\geq |w|_c \}
  6. \{w\in \{a,b\}^* \mid |w|\in 3\mathbb N \Rightarrow |w|_a = |w|_b \}